#ifndef __ConjString_H__
#define __ConjString_H__

#include <iostream>
#include <string>
#include <cassert>
using namespace std;
struct NodoConjString {
	string elemento;
	NodoConjString *siguiente;
};

struct NodoTrie {
	NodoTrie* hijos[27];
	bool fin;
};

int char2nat( char ch ) {
	return ch - 97;
}

bool hayMasRamas (const NodoTrie &n, int i) {
	int i2 = 0;
	bool retorno = false;
	while (i2 < 27 && !retorno) {
		if (i2 != i)
			retorno = (n.hijos[i2] != NULL);
		i2++;
	}
	return retorno;
}

bool esUnaHoja(const NodoTrie &n) {
	int i = 0;
	bool retorno = true;
	while ( i < 27 && retorno) {
		if (n.hijos[i] != NULL) {
			retorno = false;
		}
		i++;
	}
	return retorno;
}

void borrarRama(NodoTrie ** &n) {
	NodoTrie *aux;
	aux = *n;
	int i = 0;
	while (i != 27) {
		i = 0;
		while ((*n) -> hijos[i] == NULL && i != 27) {
			i++;
		}
		if (i != 27) {
			*n = (*n) -> hijos[i];
			delete aux;
			aux = *n;
		}
	}
	aux = *n;
	delete aux;
	*n = NULL;
}

class ConjString
{
	friend class IteradorConjString;
	friend class ConjStringTest;
	public:
		// el constructor crea el ConjString vacio
		ConjString();
		// Crea un ConjString como copia de otro. 
		ConjString(const ConjString &otro);
		// Destructor
		~ConjString();
		void agregar(const string &s);
		void eliminar(const string &s);
		bool pertenece(const string &s) const;
		int dameTamano() const;
		bool vacio() const;
		ConjString &operator=(const ConjString &otro); 
		// Imprime el ConjString en pantalla en forma legible.
		friend ostream & operator<<(ostream &o, const ConjString &esp);
	private:
		int tamano;
		NodoConjString *listaEnlazada;
		NodoTrie *trie;
};

ConjString::ConjString() {
	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;
}

ConjString::~ConjString() {
	NodoConjString *p;
	string aux;
	p = listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		eliminar(aux);
	}
}

ConjString::ConjString(const ConjString &otro) {
	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;
	NodoConjString *p;
	string aux;
	p = otro.listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		agregar(aux);
	}
}

bool ConjString::vacio() const {
	return (listaEnlazada == NULL);
}

int ConjString::dameTamano() const{
	return tamano;
}
bool ConjString::pertenece(const string &s) const {

	NodoTrie *p;
	bool retorno;
	p = trie;
	retorno = true;
	int i = 0;
	
	if ( p == NULL ) 
		retorno = false; // si el trie es nulo devuelve falso para cualquier elemento
	else {
		while (i < s.length() && retorno)  /* va a bajar en el trie hasta agotar el String */ {
			if (p -> hijos[char2nat(s[i])] == NULL ) {
				retorno = false; // si no puede seguir devuelve false
			}
			else 
				p = p -> hijos[char2nat(s[i])];
			i++;			
		}		
		if (retorno)
		retorno = p -> fin;
	}
	return retorno;
}

void ConjString::agregar(const string &s) {
	NodoTrie *p;
	int i;
	int j= 0;
	NodoConjString *p_nuevoNodo;
	if (trie == NULL) {
		trie = new NodoTrie();
		i = 0;
		while ( i < 27) {
			trie-> hijos[i] = NULL;
			i++;
		}
	}
	p = trie;
	while (j < s.length()) {
		i = 0;
		if( p -> hijos[char2nat(s[j])] == NULL ) {
			p -> hijos[char2nat(s[j])] = new NodoTrie();
			while ( i < 27) {
				(p -> hijos[char2nat(s[j])]) -> hijos[i] = NULL;
				i++;
			}			
			p -> hijos[char2nat(s[j])] -> fin = false;
		}
		p = p -> hijos[char2nat(s[j])];
		j++;
	}
	if ( p -> fin == false ) { // si no estaba ya el elemento en el conjunto {
		tamano++;
		p -> fin = true;
		// se agrega el elemento en la lista enlazada
		p_nuevoNodo = new NodoConjString();
		p_nuevoNodo -> elemento = s;
		p_nuevoNodo -> siguiente = listaEnlazada;
		listaEnlazada = p_nuevoNodo;
	}
}

void ConjString::eliminar(const string &s) {
	NodoConjString * i1;
	NodoConjString ** i2;
	bool encontrado, aux;
	NodoTrie *p, **p1;
	int i = 0;
	char proxAux, proximo;
	p = trie;
	encontrado = false;
	p1 = &trie;
	while ((i < s.length()) && (p != NULL)) {
		proxAux = s[i];
		/*	Si de este nodo que estoy considerando se desprenden más ramas que aquélla en la que se encontraría el elemento a borrar o bien 
			termina un elemento que se encuentra en el conjunto y no llegué al final del String, guardo el nodo en p1, ya que a partir de aquí
			tendré que borrar los nodos, de ser una rama de ahora en más hasta el ultimo caracter del String.
		*/
		i++;
		if ( p -> fin | hayMasRamas(*p, char2nat(proxAux)) ) {
			p1 = &(p -> hijos[char2nat(proxAux)]);
			proximo = proxAux;
		}
		p = p -> hijos[char2nat(proxAux)];	
	}
	if (p != NULL) 	{
		if ((p -> fin) && i <= s.length()) 
			encontrado = true;
	}
	// si encontramos el elemento lo eliminamos de la lista y del trie
	if (encontrado)	{
		// eliminamos el elemento de la lista
		i1 = listaEnlazada;
		i2 = &listaEnlazada;
		encontrado = false;
		while (!encontrado) {
			if ( i1 -> elemento == s) { // si encuentra el elemento
				encontrado = true;
				tamano--;
				*i2 = i1 -> siguiente;
				delete i1;
			}
			else {
				i2 = &(i1 -> siguiente);
				i1 = i1 -> siguiente;
			}
		}
		// eliminamos el elemento del trie
		if (esUnaHoja (*p)) {
			borrarRama(p1);
		}else {
			(p -> fin) = false;	
		}
	}	
}

ConjString & ConjString::operator=(const ConjString &otro) {
	if (this != &otro) {
		NodoConjString *p;
		string aux;
		p = listaEnlazada;
		while ( ! (p == NULL) ) {
			aux = p -> elemento;
			p = (p -> siguiente);
			eliminar(aux);

		}
		p = otro.listaEnlazada;
		while ( ! (p == NULL) ) {
			aux = p -> elemento;
			p = (p -> siguiente);
			agregar(aux);

		}
		
	}	
	return *this;
}


class IteradorConjString {
	public:
		IteradorConjString();
		IteradorConjString(const ConjString &c);
		string proximo();
		bool tieneProximo() const;
		IteradorConjString &operator=(const IteradorConjString &otra);
	private:
		NodoConjString *lista;
};

IteradorConjString::IteradorConjString() {
	lista = NULL;
}

IteradorConjString::IteradorConjString(const ConjString &c) {
	lista = c.listaEnlazada;
}

string IteradorConjString::proximo() {
	string aux = lista -> elemento;
	lista = lista -> siguiente;
	return aux;
}

bool IteradorConjString::tieneProximo() const {
	return (lista != NULL);
}

ostream &operator<<(ostream &o, const ConjString &esp){
	IteradorConjString it(esp);
	//cout << "Elementos del conjunto: ";
	while (it.tieneProximo()) {
		o << it.proximo() << endl;
	}
	return o;
}

IteradorConjString& IteradorConjString::operator=(const IteradorConjString &otra) {
	if (this != &otra) 
		lista = otra.lista;
	return *this;
}

#endif 
